package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/3/28 11:42
 * @DESCRIPTION
 */
// 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
// 创建一个根节点，其值为 nums 中的最大值。
// 递归地在最大值 左边 的 子数组前缀上 构建左子树。
// 递归地在最大值 右边 的 子数组后缀上 构建右子树。
// 返回 nums 构建的 最大二叉树 。

// 输入：nums = [3,2,1,6,0,5]
//     输出：[6,3,5,null,2,0,null,null,1]
//     解释：递归调用如下所示：
//     - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
//     - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
//     - 空数组，无子节点。
//     - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
//     - 空数组，无子节点。
//     - 只有一个元素，所以子节点是一个值为 1 的节点。
//     - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
//     - 只有一个元素，所以子节点是一个值为 0 的节点。
//     - 空数组，无子节点。

// 这题是 从中序与后序遍历序列构造二叉树 这道题的变形，总体思路是一样的
// 这题会更简单一点，每个子树的根节点就是数组范围内的最大值
public class ConstructMaximumBinaryTree {
    int []nums;
    public TreeNode method1(int[] nums) {
        this.nums=nums;
        return recursion(0, nums.length - 1);
    }

    public TreeNode recursion(int left,int right){
        if(left>right){
            return null;
        }
        //找到范围数组中的最大值和下标
        int[] max = findMax(left, right);
        int rootVal=max[0];
        int rootIndex=max[1];
        TreeNode root = new TreeNode(rootVal);
        TreeNode leftNode = recursion(left, rootIndex - 1);
        TreeNode rightNode = recursion(rootIndex + 1, right);
        root.left=leftNode;
        root.right=rightNode;
        return root;
    }

    //返回区间内的最大值以及对应的数组下标
    public int[] findMax(int left,int right){
        int maxValue=nums[left];
        int maxIndex=left;
        // 遍历数组，找到最大值及其下标
        for (int i = left+1; i <=right; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        return new int[]{maxValue,maxIndex};
    }
}
